package q887_superEggDrop;

import java.util.HashMap;
import java.util.Map;

public class Solution_1 {
    Map<String, Integer> memo = new HashMap<>();
    /*
    笔试中出现的一道极为经典题：
    k个鸡蛋和n层高的楼 鸡蛋在某个特定高度的楼f及更高会摔碎
    期望能够确定f是多少 返回最小操作次数
    动态规划：
    如果鸡蛋不碎，那么状态变成 (k,n−x)，即我们鸡蛋的数目不变，但答案只可能在上方的 n−x 层楼了。
    也就是说，我们把原问题缩小成了一个规模为 (k,n−x) 的子问题；
    如果鸡蛋碎了，那么状态变成 (k−1,x−1)，即我们少了一个鸡蛋
    但我们知道答案只可能在第 x 楼下方的 x−1 层楼中了。也就是说，我们把原问题缩小成了一个规模为 (k−1,x−1) 的子问题。
    这里用了二分来降低复杂度 最原始的方法是没有二分的 纯dp
     */
    public int superEggDrop(int k, int n) {
        return dp(k, n);
    }

    public int dp(int k, int n) {
        if (!memo.containsKey(n + " " + k)) {
            int ans;
            if (n == 0) {
                ans = 0;
            } else if (k == 1) {
                ans = n;
            } else {
                int lo = 1, hi = n;
                while (lo + 1 < hi) {
                    int x = (lo + hi) / 2;
                    int t1 = dp(k - 1, x - 1);
                    int t2 = dp(k, n - x);

                    if (t1 < t2) {
                        lo = x;
                    } else if (t1 > t2) {
                        hi = x;
                    } else {
                        lo = hi = x;
                    }
                }

                ans = 1 + Math.min(Math.max(dp(k - 1, lo - 1), dp(k, n - lo)), Math.max(dp(k - 1, hi - 1), dp(k, n - hi)));
            }

            memo.put(n + " " + k, ans);
        }

        return memo.get(n + " " + k);
    }
}

